package main

import (
    "fmt"
    "math/rand"
    "time"
)

func generateRandomString(length int) string {
    letters := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-=_+[]{}|;':,.<>?"

    rand.Seed(time.Now().UnixNano())
    result := make([]byte, length)
    
    for i := 0; i < length; i++ {
        result[i] = letters[rand.Intn(len(letters))]
    }
    
    return string(result)
}

func expandAroundCenter(s string, left int, right int) (int, int) {
    lenS := len(s)
    
    for left >= 0 && right < lenS && s[left] == s[right] {
        left--
        right++
    }
    
    return left + 1, right - left - 1
}

func longestPalindrome2(s string) string {
    lenS := len(s)
    start := 0
    maxLen := 0
    
    for i := 0; i < lenS; i++ {
        left1, len1 := expandAroundCenter(s, i, i)
        left2, len2 := expandAroundCenter(s, i, i+1)
        
        if len1 > maxLen {
            maxLen = len1
            start = left1
        }
        
        if len2 > maxLen {
            maxLen = len2
            start = left2
        }
    }
    
    return s[start : start+maxLen]
}

func main() {
    length := 10000000
    randomString := generateRandomString(length)
    
    start := time.Now()
    
    longestPalindrome := longestPalindrome2(randomString)
    
    elapsed := time.Since(start)
    
    fmt.Printf("Longest palindrome: %s\n", longestPalindrome)
    fmt.Printf("Time taken: %s\n", elapsed)
    
    fmt.Println("Press Enter to exit...")
    fmt.Scanln()
}